////////////////////////////////////////
// LinkedListSort.cpp

#include <iostream>
#include "LinkedListSort.h"
#include <iomanip>
using namespace std;

template <typename T>
void bubblesort(SinglyLinkedList<T> & A,
    bool (* before)(T &, T &))
{
    typename SinglyLinkedList<T>::iterator   it1, it2;
    int     k, n = A.size();
    T       temp;

	cout << "Size of list: " << n << "\n\n\n\n";

    for (int i = n - 1; i > 0; --i)
    {
        if ((k = (n - 1 - i)) % 500 == 0)
            cout << k << endl;

        for (k = 0, it2 = it1 = A.begin(), ++it2;
                k < i; ++k, it1 = it2, ++it2)

            if (!(*before)(*it1, *it2))
            {
                temp = *it1;
                *it1 = *it2;
                *it2 = temp;
            }
    }
}

/****************************************************************
*  Function: quicksort()
*  Description:
*	The quicksort() function takes in a singly linked list and a
*	pointer to a function that will be labeled "before".  quicksort()
*	is a recursive function, therefore the base case of 1 or 0 elements
*	will be the first action addressed.
*
*	Following the base case, the recursive case will be handled.
*	In that, the pivot (the first item) will be placed into its
*	own list.  Next, the rest of the original list will be divided
*	and placed into two different lists.
*
*	Once divided, quicksort will recursively call itself on the two
*	split lists.  Then the lists (Abefore, pivot, Aafter) will be
*	combined when the recursive calls return.
*
****************************************************************/
template <typename T>
void quicksort(SinglyLinkedList<T> & A, bool (* before)(T &, T &))
{
	if(A.empty() || A.oneElement()) //base case
		return;
	else //recursive case
	{
		SinglyLinkedList<T>   aAfter;
		SinglyLinkedList<T>   aBefore;
		SinglyLinkedList<T>   pivot;
		typename SinglyLinkedList<T>::iterator  aIter, pivItr;
		A.pop_front_push_other_front(pivot);
		pivItr = pivot.begin();

		//splits list into two lists by checking value against pivot
		do
		{
			aIter = A.begin();
			if(!(*before)(*aIter, *pivItr))
				A.pop_front_push_other_front(aBefore);
			else
			{
				A.pop_front_push_other_front(aAfter);
			}
			++aIter;

		}while(aIter != A.end());

		quicksort(aAfter, before);
		quicksort(aBefore, before);

		A.append_clear_other(aAfter);
		A.append_clear_other(pivot);
		A.append_clear_other(aBefore);

	}
}

